{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 函数和库"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 函数的例子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### 问题：求阶乘\\begin{equation}n!\\end{equation}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fac(n):                        # 求阶乘\n",
    "    if n == 1:                     # 收敛条件\n",
    "        return 1\n",
    "    else:\n",
    "        return n * fac(n - 1)      # 递归引用本函数的函数名\n",
    "fac(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded in comparison",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-125-eea0ffd091ad>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m9\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m                      \u001b[0;31m# 需要解决fac函数的一个bug\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 2\u001b[0;31m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mfac\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-124-e14d56a19fe5>\u001b[0m in \u001b[0;36mfac\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      3\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mfac\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m      \u001b[0;31m# 递归引用本函数的函数名\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0mfac\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "... last 1 frames repeated, from the frame below ...\n",
      "\u001b[0;32m<ipython-input-124-e14d56a19fe5>\u001b[0m in \u001b[0;36mfac\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m      3\u001b[0m         \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      4\u001b[0m     \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 5\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mn\u001b[0m \u001b[0;34m*\u001b[0m \u001b[0mfac\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mn\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m      \u001b[0;31m# 递归引用本函数的函数名\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      6\u001b[0m \u001b[0mfac\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded in comparison"
     ]
    }
   ],
   "source": [
    "for i in range(9):                      # 需要解决fac函数的一个bug\n",
    "    print(fac(i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### \\begin{equation}0!=1\\end{equation}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "fac(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### 用循环来定义阶乘函数\n",
    "```python\n",
    "def fac_loop(n):\n",
    "    ret = 1\n",
    "    for i in range(n):\n",
    "        ret = ret * (i + 1)\n",
    "    return ret\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def fac_loop(n):\n",
    "    ret = 1\n",
    "    for i in range(n):\n",
    "        ret = ret * (i + 1)\n",
    "    return ret\n",
    "print(fac_loop(5))\n",
    "print(fac_loop(0))\n",
    "print(fac_loop(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### 问题：求组合数 \\begin{equation}{n\\choose k}=\\frac{n!}{(n-k)!k!}\\end{equation}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "270725.0"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def combination(n, k):             # 求组合数\n",
    "    return fac(n) / (fac(n - k) * fac(k))\n",
    "combination(52, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 函数的类型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### 函数的类型？\n",
    "```python\n",
    "type(fac)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 127,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function"
      ]
     },
     "execution_count": 127,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(fac) # 和type(True)不是一样？"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    ">函数的类型是参数类型到返回值类型两个类型集合的映射关系\n",
    "#### \\begin{equation} fac : int→int \\end{equation}\\begin{equation} combination: int, int → int \\end{equation}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "47"
      ]
     },
     "execution_count": 128,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max([23, 37, 13, 47]) # 输入类型是一个list，输出类型是一个数值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 方法\n",
    ">第一个参数是固定函数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[13, 23, 37, 47]"
      ]
     },
     "execution_count": 129,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pl = [23, 37, 13, 47]\n",
    "pl.sort()              # 输入类型是一个list，输出类型是一个list，类型实例和函数名之间用一个.连接\n",
    "pl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 130,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on method_descriptor:\n",
      "\n",
      "sort(...)\n",
      "    L.sort(key=None, reverse=False) -> None -- stable sort *IN PLACE*\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(list.sort)        # 获得在线帮助"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[47, 37, 23, 13]"
      ]
     },
     "execution_count": 131,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pl.sort(reverse=True) # 命名参数\n",
    "pl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on class list in module builtins:\n",
      "\n",
      "class list(object)\n",
      " |  list() -> new empty list\n",
      " |  list(iterable) -> new list initialized from iterable's items\n",
      " |  \n",
      " |  Methods defined here:\n",
      " |  \n",
      " |  __add__(self, value, /)\n",
      " |      Return self+value.\n",
      " |  \n",
      " |  __contains__(self, key, /)\n",
      " |      Return key in self.\n",
      " |  \n",
      " |  __delitem__(self, key, /)\n",
      " |      Delete self[key].\n",
      " |  \n",
      " |  __eq__(self, value, /)\n",
      " |      Return self==value.\n",
      " |  \n",
      " |  __ge__(self, value, /)\n",
      " |      Return self>=value.\n",
      " |  \n",
      " |  __getattribute__(self, name, /)\n",
      " |      Return getattr(self, name).\n",
      " |  \n",
      " |  __getitem__(...)\n",
      " |      x.__getitem__(y) <==> x[y]\n",
      " |  \n",
      " |  __gt__(self, value, /)\n",
      " |      Return self>value.\n",
      " |  \n",
      " |  __iadd__(self, value, /)\n",
      " |      Implement self+=value.\n",
      " |  \n",
      " |  __imul__(self, value, /)\n",
      " |      Implement self*=value.\n",
      " |  \n",
      " |  __init__(self, /, *args, **kwargs)\n",
      " |      Initialize self.  See help(type(self)) for accurate signature.\n",
      " |  \n",
      " |  __iter__(self, /)\n",
      " |      Implement iter(self).\n",
      " |  \n",
      " |  __le__(self, value, /)\n",
      " |      Return self<=value.\n",
      " |  \n",
      " |  __len__(self, /)\n",
      " |      Return len(self).\n",
      " |  \n",
      " |  __lt__(self, value, /)\n",
      " |      Return self<value.\n",
      " |  \n",
      " |  __mul__(self, value, /)\n",
      " |      Return self*value.n\n",
      " |  \n",
      " |  __ne__(self, value, /)\n",
      " |      Return self!=value.\n",
      " |  \n",
      " |  __new__(*args, **kwargs) from builtins.type\n",
      " |      Create and return a new object.  See help(type) for accurate signature.\n",
      " |  \n",
      " |  __repr__(self, /)\n",
      " |      Return repr(self).\n",
      " |  \n",
      " |  __reversed__(...)\n",
      " |      L.__reversed__() -- return a reverse iterator over the list\n",
      " |  \n",
      " |  __rmul__(self, value, /)\n",
      " |      Return self*value.\n",
      " |  \n",
      " |  __setitem__(self, key, value, /)\n",
      " |      Set self[key] to value.\n",
      " |  \n",
      " |  __sizeof__(...)\n",
      " |      L.__sizeof__() -- size of L in memory, in bytes\n",
      " |  \n",
      " |  append(...)\n",
      " |      L.append(object) -> None -- append object to end\n",
      " |  \n",
      " |  clear(...)\n",
      " |      L.clear() -> None -- remove all items from L\n",
      " |  \n",
      " |  copy(...)\n",
      " |      L.copy() -> list -- a shallow copy of L\n",
      " |  \n",
      " |  count(...)\n",
      " |      L.count(value) -> integer -- return number of occurrences of value\n",
      " |  \n",
      " |  extend(...)\n",
      " |      L.extend(iterable) -> None -- extend list by appending elements from the iterable\n",
      " |  \n",
      " |  index(...)\n",
      " |      L.index(value, [start, [stop]]) -> integer -- return first index of value.\n",
      " |      Raises ValueError if the value is not present.\n",
      " |  \n",
      " |  insert(...)\n",
      " |      L.insert(index, object) -- insert object before index\n",
      " |  \n",
      " |  pop(...)\n",
      " |      L.pop([index]) -> item -- remove and return item at index (default last).\n",
      " |      Raises IndexError if list is empty or index is out of range.\n",
      " |  \n",
      " |  remove(...)\n",
      " |      L.remove(value) -> None -- remove first occurrence of value.\n",
      " |      Raises ValueError if the value is not present.\n",
      " |  \n",
      " |  reverse(...)\n",
      " |      L.reverse() -- reverse *IN PLACE*\n",
      " |  \n",
      " |  sort(...)\n",
      " |      L.sort(key=None, reverse=False) -> None -- stable sort *IN PLACE*\n",
      " |  \n",
      " |  ----------------------------------------------------------------------\n",
      " |  Data and other attributes defined here:\n",
      " |  \n",
      " |  __hash__ = None\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(list)             # 列出list的全部方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### 问题：伟人排序\n",
    "|像|姓名|出生年|寿命|\n",
    "|-|-|-|-|\n",
    "| ![buddha](http://bazhou.blob.core.windows.net/learning/mpp/buddha.jpg)       |  佛陀       | 480BC  |   80 |\n",
    "| ![confucius](http://bazhou.blob.core.windows.net/learning/mpp/confucius.jpg) |  孔子       | 551BC  |   73 |\n",
    "| ![plato](http://bazhou.blob.core.windows.net/learning/mpp/plato.jpg)         |  柏拉图     | 428BC  |   80 |\n",
    "| ![zoroaster](http://bazhou.blob.core.windows.net/learning/mpp/zoroaster.jpg) | 琐罗亚斯德 | 500BC  |    ?  |\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 133,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "# 新数据类型：dict\n",
    "great = [{'name':'Buddha', 'birth':-480, 'age':80}, \n",
    "         {'name':'Confucius', 'birth':-551, 'age':73}, \n",
    "         {'name':'Plato', 'birth':-428, 'age':80}, \n",
    "         {'name':'Zoroaster', 'birth':-500, 'age':float('nan')}]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Buddha'"
      ]
     },
     "execution_count": 134,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "great[0]['name'] # dict可以按照名字索引"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "73"
      ]
     },
     "execution_count": 135,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "great[1]['age']  # dict本身可以是list的元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### 无名函数\n",
    "\\begin{equation}\\lambda\\end{equation}\n",
    ">先定义一个函数再使用它有时不如在用它的地方定义它"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'name': 'Buddha', 'birth': -480, 'age': 80},\n",
       " {'name': 'Plato', 'birth': -428, 'age': 80},\n",
       " {'name': 'Confucius', 'birth': -551, 'age': 73},\n",
       " {'name': 'Zoroaster', 'birth': -500, 'age': nan}]"
      ]
     },
     "execution_count": 136,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "great = [{'name':'Buddha', 'birth':-480, 'age':80}, \n",
    "         {'name':'Confucius', 'birth':-551, 'age':73}, \n",
    "         {'name':'Plato', 'birth':-428, 'age':80}, \n",
    "         {'name':'Zoroaster', 'birth':-500, 'age':float('nan')}]\n",
    "great.sort(key=lambda person: person['age'], reverse=True) # key 参数要求一个函数类型，lambda在这里非常方便\n",
    "great"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'name': 'Confucius', 'birth': -551, 'age': 73},\n",
       " {'name': 'Zoroaster', 'birth': -500, 'age': nan},\n",
       " {'name': 'Buddha', 'birth': -480, 'age': 80},\n",
       " {'name': 'Plato', 'birth': -428, 'age': 80}]"
      ]
     },
     "execution_count": 137,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "great = [{'name':'Buddha', 'birth':-480, 'age':80}, \n",
    "         {'name':'Confucius', 'birth':-551, 'age':73}, \n",
    "         {'name':'Plato', 'birth':-428, 'age':80}, \n",
    "         {'name':'Zoroaster', 'birth':-500, 'age':float('nan')}]\n",
    "great.sort(key=lambda o: o['birth'])\n",
    "great"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 库的安装和引用"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "```sh\n",
    "pip3 install algorithms\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "```sh\n",
    "python3 -c 'from algorithms.sort import merge_sort'\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "from algorithms.sort import merge_sort\n",
    "test_list = [1, 8, 3, 5, 6]\n",
    "result_list = merge_sort(test_list)\n",
    "result_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "##### 在哪里找到这些库？\n",
    "[pypi](https://pypi.org/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "livereveal": {
   "scroll": true
  },
  "rise": {
   "enable_chalkboard": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
